using System;
using System.Collections.Generic;
using System.Text;

namespace miciv
{
    public class BlocAllocationManager
    {
        protected struct Allocation
        {
            public Allocation(int _sOffset, int _sSize)
            {
                this.m_sOffset = _sOffset;
                this.m_sSize = _sSize;
            }
            public int m_sOffset;
            public int m_sSize;
        }

        protected int m_sSize;
        protected LinkedList<Allocation> m_lnkFree;
        protected LinkedList<Allocation> m_lnkUsed;

        public BlocAllocationManager()
        {
            this.m_lnkFree = new LinkedList<Allocation>();
            this.m_lnkUsed = new LinkedList<Allocation>();
        }

        public bool Initialize(int _sSize)
        {
            this.m_sSize = _sSize;
            FreeAll();
            return true;
        }

        public bool CanAlloc(int _sRequestedSize)
        {
            foreach (Allocation freeAlloc in this.m_lnkFree)
            {
                if (_sRequestedSize <= freeAlloc.m_sSize)
                {
                    return true;
                }
            }
            return false;
        }

        public bool CanRealloc(int _sRequestedSize)
        {
            int sSize = 0;
            foreach (Allocation freeAlloc in this.m_lnkFree)
            {
                sSize += freeAlloc.m_sSize;
            }
            return (sSize >= _sRequestedSize);
        }

        public int Alloc(int _sRequestedSize)
        {
            LinkedListNode<Allocation> freeAlloc = this.m_lnkFree.First;
            while (null != freeAlloc)
            {
                if (_sRequestedSize <= freeAlloc.Value.m_sSize)
                {
                    int sOffset = freeAlloc.Value.m_sOffset;
                    bool bAddedToUsed = false;

                    LinkedListNode<Allocation> usedAlloc = this.m_lnkUsed.First;
                    while (null != usedAlloc)
                    {
                        if (usedAlloc.Value.m_sOffset > sOffset)
                        {
                            this.m_lnkUsed.AddBefore(usedAlloc, new Allocation(sOffset, _sRequestedSize));
                            bAddedToUsed = true;
                            break;
                        }
                        usedAlloc = usedAlloc.Next;
                    }
                    if (false == bAddedToUsed)
                    {
                        this.m_lnkUsed.AddLast(new Allocation(sOffset, _sRequestedSize));
                    }

                    if (0 == (freeAlloc.Value.m_sSize - _sRequestedSize))
                    {
                        this.m_lnkFree.Remove(freeAlloc);
                    }
                    else
                    {
                        freeAlloc.Value = new Allocation(freeAlloc.Value.m_sOffset + _sRequestedSize, freeAlloc.Value.m_sSize - _sRequestedSize);
                    }
                    return sOffset;
                }
                freeAlloc = freeAlloc.Next;
            }
            return -1;
        }

        public void Free(int _sOffset)
        {
            LinkedListNode<Allocation> usedAlloc = this.m_lnkUsed.First;
            while (null != usedAlloc)
            {
                if (usedAlloc.Value.m_sOffset == _sOffset)
                {
                    bool bAddedToFree = false;

                    LinkedListNode<Allocation> freeAlloc = this.m_lnkFree.First;
                    while (null != freeAlloc)
                    {
                        if ((freeAlloc.Value.m_sOffset + freeAlloc.Value.m_sSize) == usedAlloc.Value.m_sOffset)
                        {
                            freeAlloc.Value = new Allocation(freeAlloc.Value.m_sOffset, freeAlloc.Value.m_sSize + usedAlloc.Value.m_sSize);
                            bAddedToFree = true;
                            break;
                        }
                        if ((usedAlloc.Value.m_sOffset + usedAlloc.Value.m_sSize) == freeAlloc.Value.m_sOffset)
                        {
                            freeAlloc.Value = new Allocation(usedAlloc.Value.m_sOffset, freeAlloc.Value.m_sSize + usedAlloc.Value.m_sSize);
                            bAddedToFree = true;
                            break;
                        }
                        if (freeAlloc.Value.m_sOffset > usedAlloc.Value.m_sOffset)
                        {
                            this.m_lnkFree.AddBefore(freeAlloc, new Allocation(usedAlloc.Value.m_sOffset, usedAlloc.Value.m_sSize));
                            bAddedToFree = true;
                            break;
                        }
                        freeAlloc = freeAlloc.Next;
                    }

                    if (false == bAddedToFree)
                    {
                        this.m_lnkFree.AddFirst(new Allocation(usedAlloc.Value.m_sOffset, usedAlloc.Value.m_sSize));
                    }

                    this.m_lnkUsed.Remove(usedAlloc);
                    break;
                }
                usedAlloc = usedAlloc.Next;
            }
        }

        public void FreeAll()
        {
            this.m_lnkUsed.Clear();
            this.m_lnkFree.Clear();
            this.m_lnkFree.AddFirst(new Allocation(0, m_sSize));
        }
    }
}
